package org.example.myleet.p398;

import java.util.*;

public class Solution {

    private HashMap<Integer, List<Integer>> numberMapIndexes;

    private Random random;

    private int[] nums;

//    //水塘抽样法，时间换空间
//    public Solution(int[] nums) {
//        this.nums = nums;
//        random = new Random(System.currentTimeMillis());
//    }
//
//    public int pick(int target) {
//        int targetCount = 0, pick = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            if (nums[i] == target) {
//                ++targetCount;
//                if (random.nextInt(targetCount) == 0) {
//                    pick = i;
//                }
//            }
//        }
//        return pick;
//    }

    //散列表法，空间换时间
    public Solution(int[] nums) {
        numberMapIndexes = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; ++i) {
            int num = nums[i];
            List<Integer> indexes = numberMapIndexes.getOrDefault(num, new LinkedList<>());
            indexes.add(i);
            numberMapIndexes.put(num, indexes);
        }
        random = new Random(System.currentTimeMillis());
    }

    public int pick(int target) {
        List<Integer> indexes = numberMapIndexes.get(target);
        indexes = new ArrayList<>(indexes);
        numberMapIndexes.put(target, indexes);
        int i = random.nextInt(indexes.size());
        return indexes.get(i);
    }
}
